/*
 * @lc app=leetcode.cn id=502 lang=typescript
 *
 * [502] IPO
 */

// @lc code=start

class MaxPQ {
  pq: number[];
  n: number;
  constructor() {
    this.pq = [];
    this.n = 0;
  }
  private less(i: number, j: number): boolean {
    return this.pq[i] < this.pq[j];
  }
  private swap(i: number, j: number) {
    [this.pq[i], this.pq[j]] = [this.pq[j], this.pq[i]];
  }
  private swin(k: number) {
    let parentIdx = (k - 1) >> 1;
    while (parentIdx >= 0 && this.less(parentIdx, k)) {
      this.swap(parentIdx, k);
      k = parentIdx;
      parentIdx = (k - 1) >> 1;
    }
  }
  private sink(k: number) {
    let childrenIdx = k * 2 + 1;
    while (childrenIdx < this.n) {
      if (childrenIdx + 1 < this.n && this.less(childrenIdx, childrenIdx + 1)) {
        childrenIdx += 1;
      }
      if (this.less(childrenIdx, k)) return;
      this.swap(childrenIdx, k);
      k = childrenIdx;
      childrenIdx = k * 2 + 1;
    }
  }
  insert(k: number) {
    this.pq[this.n++] = k;
    this.swin(this.n - 1);
  }
  poll() {
    if (this.n === 0) return null;
    return this.pq[this.n - 1];
  }
  pop() {
    if (this.n === 0) return null;
    let max = this.pq[0];
    this.swap(0, this.n - 1);
    this.pq.pop();
    this.n--;
    this.sink(0);
    return max;
  }
}

function findMaximizedCapital(k: number, w: number, profits: number[], capital: number[]): number {
  const m = profits.length;
  const ipo = new Array(m).fill(0).map((_) => new Array(2).fill(0));
  // 保存项目的启动资金和利润
  for (let i = 0; i < m; i++) {
    ipo[i][0] = capital[i];
    ipo[i][1] = profits[i];
  }
  // 按照启动资金排序
  ipo.sort((a: number[], b: number[]) => a[0] - b[0]);

  const maxPQ = new MaxPQ();
  let idx = 0;
  // 循环k次获取项目
  for (let i = 0; i < k; i++) {
    // 将小于等于w的项目放入堆中
    while (idx < m && ipo[idx][0] <= w) {
      maxPQ.insert(ipo[idx][1]);
      idx++;
    }

    if (maxPQ.n > 0) {
      w += maxPQ.pop();
    } else {
      break;
    }
  }

  return w;
}
// @lc code=end
